# 5. 最长回文子串
# 给你一个字符串 s，找到 s 中最长的回文子串

def longestPalindrome(s: str) -> str:
    length = len(s)
    dp = [[None for _ in range(length)] for _ in range(length)]
    left = 0
    right = 0
    # 字符串长度只有1：中间斜线上的都是单个字符 True
    # 字符串长度只有2：2个字符需要特殊判断
    # i 为字符串的左边界
    # j 为字符串的右边界
    # 由于 dp[i][j] 取决于 dp[i+1][j-1]，所以行需要从下往上遍历
    for i in range(length - 1, -1, -1):
        for j in range(length - 1, -1, -1):
            if i <= j:
                # 长度为 1
                if i == j:
                    re = True
                # 长度为 2
                elif (j - i) == 1:
                    re = s[i] == s[j]
                # 长度大于 2
                else:
                    # 字符串长度超过2
                    re = dp[i + 1][j - 1] and s[i] == s[j]

                dp[i][j] = re

                # 查找最长的子串
                if re:
                    if j - i > right - left:
                        left = i
                        right = j

    return s[left:right + 1]


s_1 = "babad"
result = longestPalindrome(s_1)
print(f"result:{result}")

s_1 = "cbbd"
result = longestPalindrome(s_1)
print(f"result:{result}")

s_1 = "b"
result = longestPalindrome(s_1)
print(f"result:{result}")

s_1 = "bb"
result = longestPalindrome(s_1)
print(f"result:{result}")

s_1 = "bbb"
result = longestPalindrome(s_1)
print(f"result:{result}")

s_1 = "bbbb"
result = longestPalindrome(s_1)
print(f"result:{result}")

s_1 = "bbbbb"
result = longestPalindrome(s_1)
print(f"result:{result}")

s_1 = "bbbbbb"
result = longestPalindrome(s_1)
print(f"result:{result}")

s_1 = "bbbbbbb"
result = longestPalindrome(s_1)
print(f"result:{result}")
